/**
 * 合并两个有序链表
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 * @author yinye
 * @since 2020-03-17 18:15
 */
public class MergeTwoSortedLists {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //初始化头结点，方便后续拼接列表
        ListNode head = new ListNode(-1);
        ListNode prev = head;
        while (l1 != null && l2 != null){
            if(l1.val < l2.val){
                //直接指向l1引用，节省空间占用，可以手画指针变化过程或参考力扣官方题解，方便理解
                prev.next = l1;
                l1 = l1.next;
            }else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        prev.next = l1 != null ? l1 :l2;

        return head.next;
    }


    public static class ListNode {
          int val;
          ListNode next;
          ListNode(int x) { val = x; }

    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);

        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);

        ListNode listNode = new MergeTwoSortedLists().mergeTwoLists(l1, l2);
        while (listNode != null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

}
